\documentclass[11pt,a4paper,final,notitlepage]{article}
%\usepackage[latin1]{inputenc}
\usepackage{times}

\setlength{\hoffset}{0pt}  	
\setlength{\oddsidemargin}{0pt} 	% Marge gauche sur pages impaires
\setlength{\evensidemargin}{0pt} 	% Marge gauche sur pages paires
\setlength{\marginparwidth}{35pt} 	% Largeur de note dans la marge
\setlength{\textwidth}{450pt} 	% Largeur de la zone de texte (17cm)
\setlength{\marginparsep}{0pt} 	% Sparation de la marge
\setlength{\voffset}{0pt} 	% Bon pour DOS
\setlength{\topmargin}{0pt} 	% Pas de marge en haut
\setlength{\headheight}{0pt} 	% Haut de page
\setlength{\headsep}{0pt} 	% Entre le haut de page et le texte
\setlength{\footskip}{10pt} 	% Bas de page + sparation
\setlength{\textheight}{700pt} 	% Hauteur de la zone de texte (25cm) 
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{makeidx}
\usepackage{listings}
\usepackage{graphicx}

\begin{document}
\thispagestyle{empty}
\pagestyle{empty}

\section*{Advanced Algorithms -- Homework Set 1}

\begin{tabbing}
\textbf{Authors:} \=Valentina Sintsova (\texttt{valentina.sintsova@epfl.ch}), 
			\\ \> Javier Picorel (\texttt{javier.picorel@epfl.ch}),
			\\ \> Vasileios Trigonakis (\texttt{vasileios.trigonakis@epfl.ch})\=
\end{tabbing}
\vspace*{10pt}
\paragraph*{Question 1.} Using any of your favorite solution methods, solve the following recurrences in $\Theta$ terms.
\subparagraph*{1.} $f(n) = f (n/2)+ 2 f (n/4) +  \Theta (n)$\\

Assume that $n = 2^k$. Then this equation will be
$$f(2^k ) =f (2^{ k-1} )+ 2 f (2^{ k-2} ) +  \Theta (2^k)$$

Substitute $g(k)=f(2^k ) $:
$$g(k) = g(k-1) + 2 g(k-2) + \Theta (2^k)$$

Let's find a solution for homogeneous part
$$g(k) = g(k-1) + 2 g(k-2)$$

We try to define a solution in a form $c a^k$

$$c a^k = c a ^{k-1} + 2 c a^{k-2}$$

Dividing this equation on $c \not= 0$ and $a ^ {k-2} \not = 0$ we get

$$a^2 = a + 2 $$

which has roots $r_1 =2$ and $r_2 = -1$

So solution of homogeneous part is $c_1 2^k + c_2 (-1)^k$.

The driving function has the form $C 2^k$, that is it has the same form as one of solutions of homogeneous part. So the solution for inhomogeneous part should be in the form $P(k) 2^k$ where the degree of polynom $P$ should be increased on $1$ compared to the initial degree of polynom in driving function ($0$).

So the solution for ingomogeneous part has the form $(Ak + B) 2^k$.
Then the solution of initial equation $g(k)$ has the form $c_1 2^k + c_2 (-1)^k + c_3 k 2^k$, that is $g(k)$ is $\Theta(k 2^k)$.

Then subtituting $k = \log_2 n$ we get that $f(n)$ is $\Theta(n \log n)$.


\subparagraph*{2.} $f(n) = f (n -1) f (n - 2)$, with $f(1) = 1$ and $f(2) = 2$\\

Let's take a logarithm of the equation:

$$\log_2 {f(n)} = \log_2 {f (n -1)} + \log_2 { f (n - 2)}$$

Substitute $g(n)=\log_2 {f(n + 1)}$:
$$g(n) = g(n-1) + g(n-2)$$

$g(0) = \log_2 f (1) = \log_2 1 = 0$

$g(1) = \log_2 f (2) = \log_2 2 = 1$

The characteristic equation in this case is
$$a^2 = a + 1$$

which has roots $r_1,r_2 = \frac {1 \pm \sqrt {5}}2$

So solution of homogeneous part is $c_1 ( \frac {1 + \sqrt {5}}2)^n + c_2 ( \frac {1 - \sqrt {5}}2)^n$.

Find $c_1$ and $c_2$ from initial constraints:

$g(0) = c_1 + c_2 = 0$

$g(1) = c_1 \frac {1 + \sqrt {5}}2 + c_2  \frac {1 - \sqrt {5}}2 = 1 $

\par{\bigskip}

$c_1 = - c_2$

$c_1 - c_2 = \frac 2 {\sqrt{5}}$

\par{\bigskip}

$c_1 = \frac 1 {\sqrt{5}} $

$c_2 = - \frac 1 {\sqrt{5}} $

\par{\bigskip}

So $g(n) =\log_2 {f(n + 1)}= \frac 1 {\sqrt{5}}  ( \frac {1 + \sqrt {5}}2)^n - \frac 1 {\sqrt{5}}  ( \frac {1 - \sqrt {5}}2)^n$

$f(n) = 2^{\left( \frac 1 {\sqrt{5}} \left( \frac {1 + \sqrt {5}}2\right)^{n-1} - \frac 1 {\sqrt{5}}  \left( \frac {1 - \sqrt {5}}2\right)^{n-1}\right)}$

or $f(n) = 2^{ \frac 1 {\sqrt{5}} \left( \frac {1 + \sqrt {5}}2\right)^{n-1}}2^ {-\frac 1 {\sqrt{5}}  \left( \frac {1 - \sqrt {5}}2\right)^{n-1}}$

Because $\exists C \; \forall n \; 2^ {-\frac 1 {\sqrt{5}}  \left( \frac {1 - \sqrt {5}}2\right)^{n-1}} < C $, then 
$f(n)$ is $\Theta\left(  2^{ \frac 1 {\sqrt{5}} \left( \frac {1 + \sqrt {5}}2\right)^{n-1}} \right)$


\subparagraph*{4.} a bit harder: let $f(n) = f(n - 1)/2 + 2/f(n - 1)$, with $f(0) = 3$, and define $g(n) = \prod_{i = 1}^{n}f(i)$ (hint: guess what the answer may be and verify it using limits of ratios)
\\\\
%solution
We first calculate some values for function $f$:
\\\\
$f(0) = 3$\\\\
$f(1) = \dfrac{3}{2} + \dfrac{2}{3} = \dfrac{2^{2} + 3^{2}}{2 * 3} = 13/6$\\\\
$f(2) = \dfrac{13}{12} + \dfrac{12}{13} = \dfrac{12^{2} + 13^{2}}{12 * 13} = 313/156$\\\\
$f(3) = \dfrac{313}{312} + \dfrac{312}{313} = \dfrac{312^{2} + 313^{2}}{312 * 313}$\\\\
$\cdots$
\\\\
We recognize that the divisors $(2*3, 12*13, 312*313, ...)$ are produced by the following recurrence: $c(n) = 2c(n-1)(2c(n-1) + 1)$, with $c(0) = 1$. Replacing on $f(n)$ we get:\\
\\\\
$f(n) = \dfrac{(2c(n-1) + 1)^{2} + (2c(n-1))^{2}}{2c(n-1)(2c(n-1) + 1)} = 
\dfrac{2c(n-1) + 1}{2c(n-1)} + \dfrac{2c(n-1)}{2c(n-1) + 1} =\\\\\\
= 1 + \dfrac{1}{2c(n-1)} + \dfrac{2c(n-1) + 1 - 1}{2c(n-1) + 1} =
1 + \dfrac{1}{2c(n-1)} + 1 - \dfrac{1}{2c(n-1) + 1} =\\\\\\
= 2 + \dfrac{2c(n-1) + 1 - 2c(n-1)}{2c(n-1)(2c(n-1) + 1)} = $ \fbox{$2 + \dfrac{1}{c(n)}$}
\\\\\\
so $f(n)$ is $\Theta(2) \equiv \Theta(1)$, since $\lim_{n \rightarrow \infty}\dfrac{1}{c(n)} = 0$.
\\\\
Now, having $g(n) = \prod_{i = 1}^{n}f(i)$ we get:\\\\
$g(n) = f(1)f(2) \ldots f(n-2)f(n-1) = (2 + \dfrac{1}{c(1)})(2 + \dfrac{1}{c(2)}) \ldots (2 + \dfrac{1}{c(n-2)})(2 + \dfrac{1}{c(n-1)}) =\\\\
2^{n} + 2^{n-1} (\dfrac{1}{c(1)} + ... + \dfrac{1}{c(n)}) + 2^{n-2} (\dfrac{1}{c(1)*c(2)} + \ldots) + 2^{n-3} (\ldots) + \ldots + \dfrac{1}{c(1)* \ldots *c(n)}
$\\\\
and since $\forall n \ge 0, c(n) > 1$, we have that $g(n)$ is $\Theta(2^{n})$ if the term $2^{n}$ is the ``strongest'' in the addition.
\\\\
To prove it we prove that $\dfrac{1}{c(1)} + ... + \dfrac{1}{c(n)} = \sum_{i = 1}^{n}\dfrac{1}{c(i)} \le 1$, which will imply that any other sum in the form $\sum_{1\le i_1,..,i_k\le n}\dfrac{1}{c(i_1)c(i_2)\dots c(i_k)} = \sum_{1\le i_1,..,i_{k-1}\le n}\dfrac{1}{c(i_1)c(i_2)\dots c(i_{k-1})} \sum_{ i_k =1}^{ n} \dfrac{1}{c(i_k)} \le\\\\ \le  \sum_{1\le i_1,..,i_{k-1}\le n}\dfrac{1}{c(i_1)c(i_2)\dots c(i_{k-1})}\le \dots \le 1$
\\\\\\
We will first show that $c(n) > 2^{n}$:\\\\
$c(n) = 2c(n-1)(2(c(n-1) + 1) > 2^{2} c^{2}(n-1) > 2^{4} c^{2}(n-2) > \ldots > 2^{2n} c^{2}(0) = 2^{2n} > 2^n$ \\\\
so $\dfrac{1}{c(n)} < \dfrac{1}{2^{n}} \Rightarrow \sum_{i = 1}^{n} \dfrac{1}{c(i)} < \sum_{i = 1}^{n} \dfrac{1}{2^{i}}$
\\\\\\but $\sum_{i = 1}^{n} \dfrac{1}{2^{i}} = \dfrac{2^{n} - 1}{2^{n}} < 1$ \textbf{Q.E.D.}

\paragraph*{Question 4.} Define the following approach for the multiplication for length-n binary vectors. If we have $A = A[1 \ldots n] = A_{L}A_{R}$ and $A_{L} = A[1 \ldots n/2], A_{R} = A[n/2 + 1 \ldots n]$, then we can write $XY = 2^{n}X_{L}Y_{L} + 2^{n/2}(X_{L}Y_{R} + X_{R}Y_{L}) + X_{R}Y_{R}$. Now use this divide-and-conquer approach recursively until each vector has one element. Analyze the number of multiplications in this approach. Can you improve this approach? (Hint: $ab + cd = (a + c)(b + d) - ad - cb$)
\\\\
Define $f(n)$ the number of multiplications needed to compute the multiplication for length-n binary vectors.
Then from the definition of this multiplication $f(n)$ satisfies the following recurrence equation:

$$f(n) = 4 f (n/2) + \Theta (1)$$

Assume that $n = 2^k$. Then this equation will be

$$f(2^k ) = 4 f (2^{ k-1} )+ \Theta (1)$$

Substitute $g(k)=f(2^k ) $:

$$g(k) = 4 g(k-1) + \Theta (1)$$

This equation has solution $g(k) =  \Theta (4 ^k)$ via Master Theorem.

Subtituting $k = \log_2 n$ we get $f(n) =  \Theta (n^2)$.

\par{\bigskip}

This approach can be impoved using equation $$ab + cd = (a+c)(b+d) - cb - ad$$ that take place for defined multiplication of n-length vectors.

\begin{equation*}
\begin{split}
XY &= 2^n X_L Y_L + 2^{n/2} (X_L Y_R + X_R Y_L) + X_R Y_R =\\  
     &=2^n X_L Y_L + 2^{n/2} ((X_L + X_R)(Y_R + Y_L) - X_R Y_R - X_L Y_L) + X_R Y_R =\\
     &=(2^n - 2^{n/2} )X_L Y_L + 2^{n/2} ((X_L + X_R)(Y_R + Y_L)) + (1 -  2^{n/2} ) X_R Y_R
\end{split}
\end{equation*}

The number of multiplications in this case will follow this recurrency equation:
$$f(n) = 3 f (n/2) + \Theta (1)$$

The solution is $f(n) = \Theta (n^{\log_2 3})$ as it was deduced in the question 3.

\paragraph*{Question 5.} Matrix multiplication is easy to break into subproblems. For example, if we are given $A = 
\begin{vmatrix}
A_{11} & A_{12}\\
A_{21} & A_{22}
\end{vmatrix}
$
and $B = 
\begin{vmatrix}
B_{11} & B_{12}\\
B_{21} & B_{22}
\end{vmatrix}
$
\\then we can compute the product $AB$ as follows:
\\$AB =
\begin{vmatrix}
A_{11}B_{11} + A_{12}B_{21} & A_{11}B_{12} + A_{12}B_{22} \\
A_{21}B_{11} + A_{22}B_{21} & A_{21}B_{12} + A_{22}B_{22}
\end{vmatrix}$\\
(A and B are ($n \times n$) matrices, and Aij and Bi,j are ($n/2 \times n/2$) matrices.) Now use this divide-and-conquer approach recursively until each block has one element. Analyze the resulting number of multiplications.
\\\\\\
If $n$ is the number of elements of each matrix\footnote{for matrix $A[1..m, 1..m], n = m \times m$}, then we get the following recurrence describing the number of multiplications:
\begin{equation}
T(n) = 8T(n/4)
\end{equation}
since each multiplication is broken of 8 matrix multiplications with input the $1/4$ of the initial size.
\\This recurrence can be solved using the master theorem which gives that $T(n)$ is $\Theta(n^{\log _{4} 8}) = \Theta(n^{3/2})$
\end{document}